# _*_ utf-8 _*_
# 使用二分查找法，查找目标
"""
    二分查找法使用的前提是：列表已经升序排列
    基本原理为：
        首先将要查找的元素与列表的中间元素进行比较
            1、如果key小于中间元素，只需要在列表的前一半元素中继续查找
            2、如果key和中间元素相等，匹配成功，查找结束
            3、如果key大于中间元素，只需要在列表的后半段中继续查找key
"""
import random
from xpinyin import Pinyin
lst = []
for i in range(20):
    rand_num = random.randint(1, 101)
    while rand_num in lst:
        rand_num = random.randint(1, 101)
    lst.append(rand_num)
print("生成的随机列表为：", lst)
lst.sort()
print("排序后的lst\n", lst)

search_num = eval(input("请输入要查找的元素："))
search_index = -1
high = len(lst)
low = 0
mid = (high + low) // 2
for index in range(len(lst)):
    mid = (high + low) // 2
    if search_num == lst[mid]:
        search_index = mid
        break
    else:
        if search_num > lst[mid]:    # 说明要查找的元素在列表的后半段
            low = mid + 1
        else:
            high = mid - 1
if search_index != -1:
    print("要查找的元素{}的下标为：{}".format(search_num, search_index))
else:
    print("没有找到要查找的元素，请重试")



